#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

map<int, ListNode*> myMap;

ListNode *newList(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    myMap[index] = node;
    node->next = newList(data, index+1, size);

    return node;
}

ListNode *newList1(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    node->next = newList1(data, index+1, size);

    return node;
}

void insertList(ListNode *&node, int data)
{
    ListNode *newnode = new ListNode(data);
    if (node == NULL) {node = newnode; node->next = node; return;}//empty list;
    ListNode *cur = node;
    do {
        //cout << cur->val << " ";
        if (data >= cur->val && data <= cur->next->val) {
             newnode->next = cur->next;
             cur->next = newnode;   
             return;
        }
        if (cur->val > cur->next->val && (data <=  cur->next->val || data >= cur->val)){ //finish one loop but still could not find insert
            newnode->next = cur->next;
            cur->next = newnode; 
            return;
        }
        cur = cur->next;
    } while (cur != node);

    cout << "dam" << endl;
}

int main(int argc, char **argv)
{
    cout << "-----------------Test 1--------------------" << endl;
    vector<ListNode *> myList;
    int data[] = {1,4,9,13,15,18,20,25,29,34,56};
    ListNode *list, *list1, *print, *test;
    list = newList( data, 0, sizeof(data)/sizeof(int));
    int data2[] = {1,2,2,2,2,2,2};
    list1 = newList1( data2, 0, sizeof(data2)/sizeof(int));
    list1->next->next->next->next->next->next = list1;
    int count = 0;
    print = list;
    while(list ) {
        cout << list->val << " ";
        list= list->next;
    }
    myMap[sizeof(data)/sizeof(int)-1]->next = myMap[0];
    list = print;
    cout << endl;
    while(list && count < 20 ) {
        cout << list->val << " ";
        list= list->next;
        count ++;
    }
    cout << endl;
    cout << "-----------------Test 2--------------------" << endl;
    test = NULL;
    insertList(test, 3);
    while(test) {
        cout << test->val << " ";
        cout << endl;
        test = test->next;
    }

    cout << "-----------------Test 3--------------------" << endl;
    list = print;
    cout << endl;
    count = 0;
    insertList(myMap[3], 26);
    while(list && count < 20 ) {
        cout << list->val << " ";
        list= list->next;
        count ++;
    }
    cout << endl;

    cout << "-----------------Test 4--------------------" << endl;
    list = print;
    cout << endl;
    count = 0;
    insertList(myMap[3], 0);
    while(list && count < 20 ) {
        cout << list->val << " ";
        list= list->next;
        count ++;
    }
    cout << endl;

    cout << "-----------------Test 5--------------------" << endl;
    cout << endl;
    count = 0;
    insertList(list1, 3);
    while(list1 && count < 20 ) {
        cout << list1->val << " ";
        list1 = list1->next;
        count++;
    }
    cout << endl;
}
